package deque;

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;

public class ArrayDeque<T> implements Iterable<T>, Deque<T> {
    //创建一个泛型数组，然后给定长度，头和尾部两个指针进行操作
    private T[] array;
    private int size;
    private int front;
    private int end;

    //作为构造函数，初始化一个arraydeque
    public ArrayDeque() {
        array = (T[]) new Object[8]; // 创建数组
        size = 0;
        front = 0;
        end = 0;
    }

    public void addFirst(T item) {
        if (size == 0) {
            end++;
        }
        if (size == array.length) {
            resize();
        }
        front = (front - 1 + array.length) % array.length;
        array[front] = item;
        size++;
    }

    private void resize() {
        T[] newArray = (T[]) new Object[array.length * 2];
        for (int i = 0; i < size; i++) {
            newArray[i] = this.get(i);
        }
        array = newArray;
        front = 0;
        end = size - 1;
    }


    public void addLast(T item) {
        if (size == 0) {
            front++;
        }
        if (size == array.length) {
            resize();
        }
        end = (end + 1 + array.length) % array.length;
        array[end] = item;
        size++;
    }

    public int size() {
        return this.size;
    }

    public void printDeque() {
        for (int i = 0; i < size; i++) {
            System.out.print(get(i) + " ");
        }
    }

    //
    public T removeFirst() {
        if (size == 0) {
            return null;
        }
        T item = array[front];
        front = (front + 1 + array.length) % array.length;
        size--;
        return item;
    }

    public T removeLast() {
        if (size == 0) {
            return null;
        }
        T item = array[end];
        end = (end - 1 + array.length) % array.length;
        size--;
        return item;
    }

    public T get(int index) {
        if (index >= this.size) {
            return null;
        }
        return array[((front + index) + array.length) % array.length];
    }

    //
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            private int index = 0;  // 用于跟踪当前迭代的位置
            private int count = size();  // 记录队列中的元素数

            @Override
            public boolean hasNext() {
                return index < count;  // 检查是否还有元素可以迭代
            }

            @Override
            public T next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();  // 如果没有更多元素，抛出异常
                }
                T item = get(index);  // 获取当前索引的元素
                index++;  // 索引加1
                return item;
            }
        };
    }


    @Override
    public boolean equals(Object o) {
        // 1. 检查是否与自身比较
        if (this == o) {
            return true;
        }

        // 2. 检查传入对象是否为null或者类型是否匹配
        if (o == null || getClass() != o.getClass()) {
            return false;
        }

        // 3. 将对象强制转换为ArrayDeque
        ArrayDeque<?> other = (ArrayDeque<?>) o;

        // 4. 比较两个队列的大小是否相同
        if (this.size() != other.size()) {
            return false;
        }

        // 5. 使用两个迭代器逐一比较每个元素
        Iterator<T> thisIterator = this.iterator();
        Iterator<?> otherIterator = other.iterator();

        while (thisIterator.hasNext() && otherIterator.hasNext()) {
            T thisElement = thisIterator.next();
            Object otherElement = otherIterator.next();
            if (!Objects.equals(thisElement, otherElement)) {
                return false; // 如果任意元素不相等，返回false
            }
        }

        return true;
    }


}
